package linear

import "fmt"

// ListNode leetcode定义链表的一个节点的通用结构体
type ListNode struct {
	Val  int
	Next *ListNode
}

func (head *ListNode) PrintLinkedList() {
	for p := head; p != nil; p = p.Next {
		fmt.Print(p.Val, " ")
	}

	fmt.Println()
}

// AddTwoNumbers 两个非空的链表 1->2->3 2->3->4 ==> 3->5->7   第一想法就是这不是就是 两个有序数组合并那种写法 处理长度不等
// 非空; 保证开始的节点不是0
// [9,9,9,9,9,9,9]
// [9,9,9,9]      [不要忘记 处理最后一个进位]
// leetcode2
func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	vHead, carry := &ListNode{}, 0
	p := vHead
	for ; l1 != nil && l2 != nil; p = p.Next {
		p.Next = &ListNode{(l1.Val + l2.Val + carry) % 10, nil}
		carry = (l1.Val + l2.Val + carry) / 10

		l1 = l1.Next
		l2 = l2.Next
	}

	for ; l1 != nil; p = p.Next {
		p.Next = &ListNode{(l1.Val + carry) % 10, nil}
		carry = (l1.Val + carry) / 10

		l1 = l1.Next
	}

	for ; l2 != nil; p = p.Next {
		p.Next = &ListNode{(l2.Val + carry) % 10, nil}
		carry = (l2.Val + carry) / 10

		l2 = l2.Next
	}

	if carry == 1 {
		p.Next = &ListNode{1, nil}
	}

	return vHead.Next
}

// AddTwoNumbersV2 第二种写法 上面那是一种处理不等长的一般操作 这个通过补0 使短的等长
// leetcode2 两数相加
func AddTwoNumbersV2(l1 *ListNode, l2 *ListNode) *ListNode {
	vHead, carry := &ListNode{}, 0
	p := vHead
	for ; l1 != nil || l2 != nil; p = p.Next {
		var d1, d2 int
		if l1 == nil {
			d1 = 0
		} else {
			d1 = l1.Val
			l1 = l1.Next
		}

		if l2 == nil {
			d2 = 0
		} else {
			d2 = l2.Val
			l2 = l2.Next
		}

		p.Next = &ListNode{(d1 + d2 + carry) % 10, nil}
		carry = (d1 + d2 + carry) / 10
	}

	if carry == 1 {
		p.Next = &ListNode{1, nil}
	}

	return vHead.Next
}

// RemoveNthFromEnd 删除链表的倒数第n个节点
// leetcode19 删除链表的倒数第n个节点
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	var (
		head0 = &ListNode{0, head}
		cnt   = 0
		p     = head0
		s     = head0
	)

	// 需要找到指定节点的上一个节点才行
	for cnt < n {
		p = p.Next
		cnt++
	}

	for p.Next != nil {
		p = p.Next
		s = s.Next
	}

	t := s.Next.Next
	s.Next.Next = nil // help gc
	s.Next = t

	return head0.Next
}

var cn = 0

// RemoveNthFromEndV2 删除倒数第n个节点 使用递归来解 第一次
// leetcode19 删除链表的倒数第n个节点 利用递归 利用方法栈出栈的次数 需要定义全局变量
// leetcode 全局变量有问题 操
func RemoveNthFromEndV2(head *ListNode, n int) *ListNode {
	// 递归一定会有 结束的边界
	if head == nil {
		return head
	}

	head.Next = RemoveNthFromEndV2(head.Next, n)
	cn++
	if cn == n {
		return head.Next
	}

	return head
}

// MergeTwoLists 合并两个有序列表
// leetcode21 合并两个有序列表  又可以使用递归 我透了
func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	var (
		l  = &ListNode{}
		p  = l
		p1 = l1
		p2 = l2
	)

	for ; p1 != nil && p2 != nil; p = p.Next {
		if p1.Val < p2.Val {
			p.Next = p1
			p1 = p1.Next
		} else {
			p.Next = p2
			p2 = p2.Next
		}
	}

	if p1 != nil {
		p.Next = p1
	}

	if p2 != nil {
		p.Next = p2
	}

	return l.Next
}

// MergeKLists 合并k个有序链表
// leetcode23 合并k个有序链表 Level diff;
// 妈的我做这个题目真的就是喜欢玩这种 conquer and merge
func MergeKLists(lists []*ListNode) *ListNode {
	if lists == nil {
		return nil
	}

	if len(lists) == 1 {
		return lists[0]
	}

	mid := len(lists) >> 1
	l := MergeKLists(lists[:mid])
	r := MergeKLists(lists[mid:])
	return MergeTwoLists(l, r)
}

// SwapPairs 交换相邻的节点
// leetcode24 交换相邻的节点
// 一般做法 感觉下面写法很怪 明天再写 并且把递归的也写了了
func SwapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	head0 := &ListNode{0, head}
	for p := head0; p.Next != nil && p.Next.Next != nil; p = p.Next.Next {
		// 第二个节点
		p2 := p.Next.Next
		// 让第一个节点指向 第二个节点的下一个节点
		p.Next.Next = p2.Next
		// 让第二个节点指向 第一个节点
		p2.Next = p.Next
		// 让头节点指向第二个节点
		p.Next = p2
	}
	return head0.Next
}

// SwapPairsV2 使用递归
func SwapPairsV2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	head.Next.Next = SwapPairsV2(head.Next.Next)
	newHead := head.Next
	head.Next = newHead.Next
	newHead.Next = head
	return newHead
}

// ReverseKGroup K 个一组翻转链表
// leetcode25 Level: diff
func ReverseKGroup(head *ListNode, k int) *ListNode {
	p := head
	for cnt := 0; cnt < k; p = p.Next {
		if p != nil {
			cnt++
		} else {
			return head
		}
	}

	newHead := ReverseKGroup(p, k)
	res := ReverseK(head, k)
	head.Next = newHead
	return res
}

func ReverseK(head *ListNode, k int) *ListNode {
	res := &ListNode{}
	p := head
	for cnt := 0; cnt < k; cnt++ {
		subHead := res.Next
		res.Next = p
		// p这时候一定要右移
		p = p.Next
		res.Next.Next = subHead
	}

	return res.Next
}
